Nelson Mandela thuộc chi nhỏ nhất của dòng họ phong kiến Thembu, trị vì các lãnh thổ Transkei thuộc tỉnh Cape của Nam Phi.[3] Ông sinh ra tại Mvezo, một ngôi làng nhỏ thuộc huyện Umtata, thủ phủ của Transkei.[3] Ông cố ruột Ngubengcuka của ông (mất năm 1832) đã trị vì với danh hiệu Inkosi Enkhulu, tức là vua của người Thembu.[4] Một trong những con trai của nhà vua, có tên là Mandela, chính là ông nội của Nelson và đây chính là nguồn gốc họ Mandela của ông. Tuy nhiên, vì ông là con trai của Inkosi với một người vợ thuộc bộ tộc Ixhiba (gọi là "Tả gia"[5]), các con cháu thuộc chi này tuy vẫn thuộc Hoàng gia nhưng không bao giờ được thừa kế ngai vàng Thembu.

Cha của Nelson Mandela, Gadla Henry Mphakanyiswa, là người đứng đầu bộ lạc ở thị trấn Mvezo.[6] Tuy vậy, do không được chính quyền thuộc địa vừa lòng, Mphakanyiswa bị tước chức và cả gia đình bị chuyển đến Qunu. Dù vậy, Mphakanyiswa vẫn là thành viên Hội đồng Cơ mật của Inkosi, và đóng vai trò là người hỗ trợ cho Jongintaba Dalindyebo lên ngôi quốc vương Thembu. Dalindyebo sau này đã trả ơn ông bằng cách nhận nuôi Mandela sau khi Mphakanyiswa chết.[7] Cha của Mandela có bốn bà vợ, sinh tổng cộng 13 người con (bốn trai, chín gái).[7] Mandela là con của bà vợ thứ ba, Nosekeni Fanny. Fanny là con của Nkedama thuộc bộ tộc Mpemvu Xhosa, thuộc về nhà Hữu gia, là vùng đất nơi Mandela đã trải qua phần lớn thời thơ ấu.[8] Tên của ông Rolihlahla có nghĩa là "kéo cành cây", hay một cách thông tục, có nghĩa là "kẻ gây rối".[9][10]

Rolihlahla Mandela là người đầu tiên trong gia đình được đi học, tại đó cô giáo Mdingane đã đặt cho ông một cái tên tiếng Anh là "Nelson".[11]

Lúc Mandela lên chín, cha ông qua đời vì bệnh lao phổi, quan nhiếp chính Jongintaba trở thành người giám hộ hợp pháp của ông.[7] Mandela đi học trường truyền giáo thuộc Hội Giám lý nằm kế bên lâu đài của quan nhiếp chính. Theo phong tục của người Thembu, ông được thụ giáo lúc 16 tuổi, rồi đi học Học viện Clarkebury Boarding.[12] Mandela đã hoàn tất Bằng sơ trung học chỉ trong vòng hai năm, thay vì ba năm như thông thường.[12] Để chuẩn bị thừa kế vị trí thành viên Hội đồng Cơ mật của cha mình, năm 1937, Mandela chuyển đến trường Healdtown, ngôi trường tại Fort Beaufort, nơi hầu hết con cháu hoàng tộc Thembu đều đi học.[13] Vào lúc 19 tuổi, ông bắt đầu quan tâm đến bộ môn quyền anh và chạy bộ tại trường.[8]

Sau đó, ông đậu vào học bằng Cử nhân tại Trường Đại học Fort Hare, nơi ông đã gặp Oliver Tambo. Tambo và Mandela sau này là những người bạn và đồng nghiệp thân thiết. Mandela cũng kết bạn với người bà con Kaiser ("K.D.") Matanzima, người thuộc dòng trực hệ của Hữu gia của người Thembu, là người thừa kế ngai vàng Transkei[5], vì vai trò mà sau đó đã đưa ông đến với chính sách Bantustan. Chính sự ủng hộ chính sách này của ông và Mandela đã khiến hai người trở thành phe chính trị đối lập.[8] Cuối năm thứ nhất, Mandela tham gia vào vụ tẩy chay của Hội sinh viên nhằm chống lại quy định của trường đại học, và bị buộc phải rời trường Fort Hare không được trở lại chừng nào ông chưa chấp nhận cuộc bầu cử của vào Hội.[14] Sau này, lúc ở trong tù, Mandela đã học bằng Cử nhân luật của Chương trình đào tạo từ xa của Đại học Luân Đôn.

Một thời gian ngắn sau khi rời Fort Hare, Jongintaba đã thông báo với Mandela và Justice (con của quan nhiếp chính và là người thừa kế ngai vàng) rằng ông đã sắp xếp đám cưới cho cả hai người. Những thanh niên trẻ không vừa lòng với sự sắp đặt này, và quyết định chuyển đến sống ở Johannesburg.[15] Khi đến Johannesburg, Mandela xin một chân canh gác tại một khu mỏ.[16] Tuy nhiên, ông chủ lập tức đuổi việc Mandela khi hay rằng ông là con nuôi đang chạy trốn của Quan nhiếp chính. Mandela chuyển sang làm tập sự ở một công ty luật ở Johannesburg, Witkin, Sidelsky và Edelman, nhờ quen biết với một người bạn và người hướng dẫn, nhân viên địa ốc Walter Sisulu.[16] Khi làm việc tại hãng Witkin, Sidelsky và Edelman, Mandela đã hoàn tất tấm bằng Cử nhân hàm thụ của Trường Đại học Nam Phi, sau đó ông học luật tại Trường Đại học Witwatersrand, tại đó ông kết bạn tới bạn học mà sau này là đồng chí chống chủ nghĩa apartheid của ông Joe Slovo, Harry Schwarz và Ruth First. Slovo sau này là Bộ trưởng Bộ cư trú, còn Schwarz là Đại sứ Nam Phi tại Hoa Kỳ. Trong thời gian này, ông sống tại thành phố ngoại ô Alexandra, phía bắc Johannesburg.[17]